#pragma once
#include <type_traits>
#include <iostream>
using std::ostream;

#include "../public/constants.hpp"
#include "../public/exception.hpp"
#include "../allocator/defaloc.hpp"
#include "../iterator/iterator_traits.hpp"

namespace bla {
	template<typename _type>
	class list;

	//class data inner struct define: size of listNode class: 8 + sizeof(_type)
	//WARNING: when use _listNode* as pointer, and use malloc, 
	//    then just after must construct(call placement new of _type if necessary) before use listnode
	//         when use _listNode* as pointer, and use free, 
	//    then right before must destroy(call ~_type if necessary)
	template<typename _type>
	struct _listNode
	{
		_type _val;
		_listNode* _next;
		_listNode* _prev;
		_listNode() : _val(_type()), _next(nullptr), _prev(nullptr) { ; };
		_listNode(_type p) : _val(p), _next(nullptr), _prev(nullptr) { ; };
	};

	/*
	 * template para:
	 * _type : all container have, can be any type
	 * note: considering some FUCK thing, I remove the allocator template para of listIterator and list,
	 *     directedly use the default allocator
	 */
	template<typename _type>
	class listIterator {
		friend class list<_type>;
	public:
		//using define
		using valueType = _type;
		using pointerType = _type * ;
		using referenceType = _type & ;
		using sizeType = _containerSizeType;
		using differenceType = _containerSizeType;

		//interface of all iteraters
		typedef valueType _valueType;
		typedef differenceType _difType;
		typedef _si_direction_iterator_flag _category;
	private:
		//predefined type/value
		typedef _listNode<_type> _Node;
		const sizeType _typeSize = sizeof(_Node);
	private:
		//class data define: size of listIterator<> class: 8
		_Node* _ptrdata;
	public:
		listIterator(_Node* d = nullptr) :_ptrdata(d){; };
		listIterator(const listIterator<_type>& li) {
			this->_ptrdata = li._ptrdata;
		}
		listIterator<_type>& operator=(const listIterator<_type>& li) {
			if (&li == this) return *this;
			else {
				this->_ptrdata = li._ptrdata;
				return *this;
			}
		}

		referenceType operator *() { return this->_ptrdata->_val; }
		const referenceType operator *()const { return this->_ptrdata->_val; }
		pointerType operator ->() { return &(operator*()); }
		const pointerType operator ->()const { return &(operator*()); }

		listIterator<_type>& operator ++() {
			this->_ptrdata = this->_ptrdata->_next;
			return *this;
		};
		listIterator<_type> operator ++(int) {
			auto temp = *this;
			++(*this);
			return temp;
		};
		listIterator<_type>& operator --() {
			this->_ptrdata = this->_ptrdata->_prev;
			return *this;
		};
		listIterator<_type> operator --(int) {
			auto temp = *this;
			--(*this);
			return temp;
		};
	public:
		template<typename _type>
		friend bool operator ==(const listIterator<_type>& lhs, const listIterator<_type>& rhs);

		template<typename _type>
		friend bool operator !=(const listIterator<_type>& lhs, const listIterator<_type>& rhs);

		template<typename _type>
		friend listIterator<_type> operator+ (
			const listIterator<_type>& it, typename listIterator<_type>::differenceType n);

		template<typename _type>
		friend listIterator<_type> operator+ (
			typename listIterator<_type>::differenceType n, const listIterator<_type>& it);

		template<typename _type>
		friend listIterator<_type> operator- (
			const listIterator<_type>& it, typename listIterator<_type>::differenceType n);

		template<typename _type>
		friend listIterator<_type> operator- (
			typename listIterator<_type>::differenceType n, const listIterator<_type>& it);

		template<typename _type>
		friend typename listIterator<_type>::differenceType operator- (
			const listIterator<_type>& it1, const listIterator<_type>& it2);

	public:
		~listIterator() {
			;
		}
	};

	template<typename _type>
	bool operator==(const listIterator<_type>& lhs, const listIterator<_type>& rhs){
		return lhs._ptrdata == rhs._ptrdata;
	}

	template<typename _type>
	bool operator!=(const listIterator<_type>& lhs, const listIterator<_type>& rhs){
		return !(lhs == rhs);
	}

	template<typename _type>
	listIterator<_type> operator+(const listIterator<_type>& it, typename listIterator<_type>::differenceType n)
	{
		listIterator<_type> ret(it);
		for (typename listIterator<_type>::differenceType i = 0; i < n; ++i) {
			ret++;
		}
		return ret;
	}

	template<typename _type>
	listIterator<_type> operator+(typename listIterator<_type>::differenceType n, const listIterator<_type>& it)
	{
		listIterator<_type> ret(it);
		for (typename listIterator<_type>::differenceType i = 0; i < n; ++i) {
			ret++;
		}
		return ret;
	}

	template<typename _type>
	listIterator<_type> operator-(const listIterator<_type>& it, typename listIterator<_type>::differenceType n)
	{
		listIterator<_type> ret(it);
		for (typename listIterator<_type>::differenceType i = 0; i < n; ++i) {
			ret--;
		}
		return ret;
	}

	template<typename _type>
	listIterator<_type> operator-(typename listIterator<_type>::differenceType n, const listIterator<_type>& it)
	{
		listIterator<_type> ret(it);
		for (typename listIterator<_type>::differenceType i = 0; i < n; ++i) {
			ret--;
		}
		return ret;
	}

	//note: it2 must >= it1
	template<typename _type>
	typename listIterator<_type>::differenceType operator-(const listIterator<_type>& it1, const listIterator<_type>& it2)
	{
		listIterator<_type> preIter(it2);
		typename listIterator<_type>::differenceType ret = 0;
		while (preIter != it1) {
			ret++;
			preIter++;
		}
		return ret;
	}

	/*
	 * template para:
	 * _type : all container have, can be any type
	 * note: considering some FUCK thing, I remove the allocator template para of listIterator and list
	 *     should use the default allocator
	 */
	template<typename _type>
	class list {
		friend class listIterator<_type>;
	public:
		//using define
		using iterator = listIterator<_type>;
		using sizeType = _containerSizeType;
		using differenceType = _containerSizeType;
		using valueType = _type;
		using pointerType = _type * ;
		using referenceType = _type & ;
	private:
		//predefined type/value
		//const sizeType _typeSize = sizeof(_listNode<_type>);
		typedef _defaloc<_listNode<_type>> _allocator;
	private:
		//class data define: size of list<> class: 24
		sizeType _size;
		iterator _head;
		iterator _tail;
		_allocator _allocatorObject;  //use the dafault allocator
	public:
		inline const sizeType size() const { return this->_size; };
		inline bool empty() const { return this->_size == 0; };

		inline const iterator head() const { return this->_head; };
		inline const iterator tail() const { return this->_tail; };
		inline iterator head() { return this->_head; };
		inline iterator tail() { return this->_tail; };

		inline const iterator begin() const { return iterator(this->_head._ptrdata->_next); };
		inline const iterator end() const { return this->_tail; };
		inline iterator begin() { return iterator(this->_head._ptrdata->_next); };
		inline iterator end() { return this->_tail; };

		/*
		 * push_back: const valueType& v
		 *     add a value/object in the end
		 */
		void push_back(const valueType& v) {
			_listNode<valueType>* newNode = _allocatorObject._allocate(1);
			if (!std::is_trivially_copy_constructible<_type>::value) {
				_allocatorObject._construct(newNode, valueType());
			}
			(this->_tail._ptrdata)->_val = v;
			(this->_tail._ptrdata)->_next = newNode;
			newNode->_prev = this->_tail._ptrdata;
			this->_tail._ptrdata = newNode;
			this->_size++;
		}

		/*
		 * pop_back:
		 *     if not empty, remove a value/object in the end, return true
		 *     else return false
		 */
		bool pop_back() {
			if (this->empty()) return false;
			else {
				_listNode<valueType>* newTail = (this->_tail._ptrdata)->_prev;
				newTail->_next = nullptr;
				if (!std::is_trivially_destructible<_type>::value) {
					_allocatorObject._destroy(this->_tail._ptrdata);
				}
				_allocatorObject._deallocate(this->_tail._ptrdata);
				this->_tail._ptrdata = newTail;
				this->_size--;
				return true;
			}
		}

		/*
		 * insert: iterator it, const valueType& v
		 *     add a value/object at it
		 * note: it should not be the head(dump) node of list, I donnot check it!
		 */
		void insert(iterator it, const valueType& v) {
			_listNode<valueType>* newNode = _allocatorObject._allocate(1);
			_listNode<valueType>* prevNode = it._ptrdata->_prev; //since not head, this cannot be nullptr
			newNode->_val = v;
			newNode->_prev = prevNode;
			prevNode->_next = newNode;
			newNode->_next = it._ptrdata;
			it._ptrdata->_prev = newNode;
			this->_size++;
		}

		/*
		 * insert: iterator it, iterator ista, iterator iend
		 *     add some value/objects at it
		 * note: it should not be the head(dump) node of list, I donnot check it!
		 * ista and iend should not belong to *this, ista and iend should belong to the same thing, I donnot check it!
		 * ista should < iend, I donnot check it!
		 */
		void insert(iterator it, iterator ista, iterator iend) {
			//create the connection of ista and iend
			_listNode<valueType>* newNodeBegin = _allocatorObject._allocate(1);
			newNodeBegin->_val = *ista;
			this->_size++;
			ista++;
			_listNode<valueType>* newNodeEnd;
			if (ista == iend) {
				newNodeEnd = newNodeBegin;
			}
			else {
				_listNode<valueType>* newNodePre = nullptr; //dump, I make sure that the following for loop will loop > 1
				_listNode<valueType>* newNodeOld = newNodeBegin;

				for (iterator iter = ista; iter != iend; ++iter) {
					newNodePre = _allocatorObject._allocate(1);
					newNodePre->_val = *iter;
					newNodeOld->_next = newNodePre;
					newNodePre->_prev = newNodeOld;
					newNodeOld = newNodePre;
					this->_size++;
				}
				newNodeEnd = newNodePre;
			}

			_listNode<valueType>* prevNode = it._ptrdata->_prev; //since not head, this cannot be nullptr
			newNodeBegin->_prev = prevNode;
			prevNode->_next = newNodeBegin;
			newNodeEnd->_next = it._ptrdata;
			it._ptrdata->_prev = newNodeEnd;
		}

		/*
		 * erase: const valueType& v
		 *     remove a value/object of it
		 * note: it should not be the head(dump)/end node of list, I donnot check it!
		 */
		void erase(iterator it) {
			_listNode<valueType>* prevNode = it._ptrdata->_prev; //since not head, this cannot be nullptr
			_listNode<valueType>* nextNode = it._ptrdata->_next; //since not tail, this cannot be nullptr
			prevNode->_next = nextNode;
			nextNode->_prev = prevNode;
			_allocatorObject._deallocate(it._ptrdata);
			this->_size--;
		}

		/*
		 * erase: iterator sta, iterator end
		 *     remove sta to end
		 * note: it should not include head(dump) node of list, I donnot check it!
		 * note: sta and end should belong to this, I donnot check it!
		 * sta should < end, I donnot check it!
		 */
		void erase(iterator sta, iterator end) {
			_listNode<valueType>* prevNode = sta._ptrdata->_prev; //since not head, this cannot be nullptr
			_listNode<valueType>* nextNode = end._ptrdata;
			for (iterator iter = sta; iter != end;) {
				_listNode<valueType>* tempnext = iter._ptrdata->_next;
				_allocatorObject._deallocate(iter._ptrdata);
				this->_size--;
				iter = tempnext;
			}
			prevNode->_next = nextNode;
			nextNode->_prev = prevNode;
		}

		/*
		 * default construction function:
		 *     init private values,
		 */
		list() :
			_size(0), _head(listIterator<_type>()),
			_tail(listIterator<_type>()),
			_allocatorObject(_allocator())
		{
			this->_head._ptrdata = _allocatorObject._allocate(1); //must allocate the dump head node in construction
			this->_tail._ptrdata = _allocatorObject._allocate(1); //must allocate the dump head node in construction
			if (!std::is_trivially_copy_constructible<_type>::value) {
				_allocatorObject._construct(this->_head._ptrdata, _type());
				_allocatorObject._construct(this->_tail._ptrdata, _type());
			}
			
			this->_head._ptrdata->_next = this->_tail._ptrdata;
			this->_tail._ptrdata->_prev = this->_head._ptrdata;
		}

		/*
		 * copy construction function:
		 */
		list(const list<_type>& _cpf) :
			_size(0), _head(listIterator<_type>()),
			_tail(listIterator<_type>()),
			_allocatorObject(_allocator())
		{
			this->_head._ptrdata = _allocatorObject._allocate(1); //must allocate the dump head node in construction
			this->_tail._ptrdata = _allocatorObject._allocate(1); //must allocate the dump head node in construction
			if (!std::is_trivially_copy_constructible<_type>::value) {
				_allocatorObject._construct(this->_head._ptrdata, _type());
				_allocatorObject._construct(this->_tail._ptrdata, _type());
			}
			this->_head._ptrdata->_next = this->_tail._ptrdata;
			this->_tail._ptrdata->_prev = this->_head._ptrdata;

			for (iterator it = _cpf.begin(); it != _cpf.end(); ++it) {
				this->push_back(*it);
			}
		}

		/*
		 * = assign function
		 *  compare &_cpf and this first, if address of these two pointers are same, do nothing
		 *                                if not, copy value/objects
		 *                                    and push_back/pop_back
		 */
		list<_type>& operator= (const list<_type>& _cpf) {
			if (&_cpf == this)
				return *this;
			else {  
				iterator _rawit = this->begin();
				iterator _cpit = _cpf.begin();
				const iterator _rawitend = this->end();
				const iterator _cpitend = _cpf.end();
				while (_rawit != _rawitend && _cpit != _cpitend)
				{
					*(_rawit++) = *(_cpit++);
				}
				if (_rawit != _rawitend) {  //*this is more longer
					while (_rawit != this->end()) { //call pop_back
						this->pop_back(); //will modify this->_tail inside
					}
				}
				else {  //_cpf is more longer
					while (_cpit != _cpitend) { //call push_back
						this->push_back(*(_cpit++));
					}
				}
				this->_size = _cpf.size();
				return *this;
			}
		}

		/*
		 * deconstruction function:
		 */
		~list() {
			while (this->begin() != this->_tail) { //call pop_back
				this->pop_back(); //will modify this->_tail inside
			}
			if (!std::is_trivially_destructible<_type>::value) {
				_allocatorObject._destroy(this->_head._ptrdata);
				_allocatorObject._destroy(this->_tail._ptrdata);
			}
			_allocatorObject._deallocate(this->_head._ptrdata);
			_allocatorObject._deallocate(this->_tail._ptrdata);
		}

		template<typename _type>
		friend ostream& operator<< (ostream &os, const list<_type>& li);
	};

	template<typename _type>
	ostream & operator<<(ostream & os, typename const list<_type>& a)
	{
		typename list<_type>::iterator iter = a.begin();
		for (; iter != a.end(); ++iter) {
			os << *iter << " ";
		}
		return os;
	}
}
